package com.booby.algorithm.merge;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 归并排序，从小到大
 *
 * @author: lizt
 * @date: 2020/8/23 15:51
 **/

public class MinToMax {

    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};

    public static void sorted(Integer[] arr, int left, int right){
        if (left == right){
            return;
        }
        // 一般写 （left + right）/ 2  容易超出整型范围
        int mid = left + (right-left)/2;
        sorted(arr, left, mid);
        sorted(arr, mid + 1, right);
        merge(arr, left, mid + 1, right);
    }
    public static void merge(Integer[] arr, int leftPtr, int rightPtr, int rightBound){
        Integer[] temp = new Integer[rightBound - leftPtr + 1];
        int mid = rightPtr - 1;
        int index = 0;
        int left = leftPtr;
        int right = rightPtr;
        while (left <= mid && right <= rightBound) {
            if (arr[left] <= arr[right]) {
                temp[index] = arr[left];
                left++;
                index++;
            }else {
                temp[index] = arr[right];
                index++;
                right++;
            }
        }
        while (left <= mid){
            temp[index] = arr[left];
            left++;
            index++;
        }

        while (right <= rightBound){
            temp[index] = arr[right];
            right++;
            index++;
        }

        for (int i = 0; i < temp.length; i++) {
            arr[leftPtr + i] = temp[i];
        }

    }
    public static void main(String[] args) {
        sorted(arr, 0, arr.length -1);
        Utils.print(arr);
    }
}
